import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
    public int numberOfArithmeticSlices(int[] nums) {
        if(nums.length<3) return 0;
        int n=nums.length;
        int[] dp=new int[n];
        int ret=0;
        for(int i=2;i<n;i++){
            if(nums[i]-nums[i-1]==nums[i-1]-nums[i-2]){
                dp[i]=dp[i-1]+1;
            }
            ret+=dp[i];
        }
        return ret;
    }
    public int maxTurbulenceSize(int[] arr) {
        int n=arr.length;
        int[][] dp=new int[n][2];
        dp[0][1]=dp[0][0]=1;
        int maxLen=1;
        for(int i=1;i<n;i++){
            dp[i][0]=dp[i][1]=1;
            if(arr[i-1]>arr[i]){
                dp[i][0]=dp[i-1][1]+1;
            }
            else if(arr[i-1]<arr[i]){
                dp[i][1]=dp[i-1][0]+1;
            }
            maxLen=Math.max(maxLen,dp[i][1]);
            maxLen=Math.max(maxLen,dp[i][0]);
        }
        return maxLen;
    }
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> hash=new HashSet<>(wordDict);
        int n=s.length();
        boolean[] dp=new boolean[n+1];
        dp[0]=true;
        for(int i=1;i<=n;i++){
            for(int j=0;j<i;j++){
                if(dp[j]&&hash.contains(s.substring(j,i))){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[n];
    }
    public int findSubstringInWraproundString(String s) {
        int[] hash=new int[26];
        int n=s.length();
        int[] dp=new int[n];
        dp[0]=1;
        for(int i=0;i<n;i++){
            dp[i]=1;
            if(i>0&&(s.charAt(i)-s.charAt(i-1)==1||(s.charAt(i)=='a'&&s.charAt(i-1)=='z'))){
                dp[i]=dp[i-1]+1;
            }
            hash[s.charAt(i)-'a']=Math.max( hash[s.charAt(i)-'a'],dp[i]);
        }
        return Arrays.stream(hash).sum();
    }
}